package com.ruoyi.learn.java.algorithm.sort;

public class BubbleSort {
    // 冒泡排序方法

    /**
     * 冒泡排序算法的时间复杂度在不同情况下有所不同：
     * 最坏情况：当输入数组是完全逆序时，需要进行最多的比较和交换操作。此时时间复杂度为 O(n²)，其中 n 是数组中元素的数量。
     * 最好情况：当输入数组已经是有序状态时，如果对算法进行优化（加入一个标志位判断是否发生交换，若未交换则提前结束排序），时间复杂度可以优化到 O(n)。
     * 平均情况：对于随机排列的数组，冒泡排序的平均时间复杂度仍然是 O(n²)。
     * 这是因为冒泡排序本质上是通过嵌套循环实现的：外层循环需要执行 O (n) 次，内层循环在最坏情况下也需要执行 O (n) 次，因此整体呈现平方级的时间复杂度。这种特性使得冒泡排序在处理大规模数据时效率较低，通常适用于小规模数据或作为排序算法的入门学习案例。
     *
     * 空间复杂度
     * 冒泡排序是一种原地排序算法，排序过程中只需要一个临时变量用于交换元素，不需要额外的存储空间，因此空间复杂度为 O(1)。
     * 稳定性
     * 冒泡排序是稳定的排序算法，因为当两个元素相等时，不会进行交换，保持了它们原有的相对顺序。
     * 总结来说，冒泡排序的时间复杂度为 O (n²)（平均和最坏情况），空间复杂度为 O (1)，适合小规模数据的排序场景。
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

        // 外层循环控制排序轮数
        for (int i = 0; i < n - 1; i++) {
            // 内层循环控制每轮比较次数
            // 每轮结束后，最大的元素已"浮"到末尾，下轮可减少一次比较
            for (int j = 0; j < n - i - 1; j++) {
                // 如果当前元素大于下一个元素，则交换它们
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] testArray = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前的数组:");
        printArray(testArray);

        // 调用冒泡排序
        bubbleSort(testArray);

        System.out.println("排序后的数组:");
        printArray(testArray);
    }
}
